#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "QuickSort.h"
#define MAXCOUNT 2000000

//测试数据
int aTempData[MAXCOUNT];
int aTestData[MAXCOUNT];

//产生预定个数的随机数。
void initTestData() {
	for (int i = 0; i < MAXCOUNT; i++) {
		aTestData[i] = rand();
	}
}


//quickSort()测试1：递归快速排序调试版。
void Test1() {
	//int aTestData[] = {5, 2, 3, 5, 7, 3, 8, 6, 4, 9};
	//int aTestData[] = {5, 2, 3, 5, 7, 3, 8, 6, 4, 9, 15, 12, 32, 51, 75, 23, 8, 62, 24, 19, 15, 222, 343, 53, 67, 34, 83, 68, 46, 39};

	int iLen = sizeof(aTestData)/sizeof(aTestData[0]);
	printf("len=%i\n\n", iLen);

	int iCount = 0;
	int iHoleCount = 0;
	printf("原始数据：\n");
	printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");

	iCount = quickSort_Test(aTestData, 0, iLen-1, &iHoleCount);
	printf("共比较了%i次，共挖了%i个坑填满，排序后：\n", iCount, iHoleCount);
	printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");
}

//quickSort()测试2：递归快速排序正式版。
void Test2() {
	clock_t start_t, end_t;
	double total_t;

	int iLen = sizeof(aTestData)/sizeof(aTestData[0]);
	printf("len=%i\n\n", iLen);

	printf("递归快速排序，原始数据：\n");
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");

	start_t = clock();
	quickSort(aTestData, 0, iLen-1);
	end_t = clock();
	total_t = (double)(end_t - start_t) / CLOCKS_PER_SEC;

	printf("耗时=%fs,排序后：\n", total_t);
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");
}

//栈测试
void Test_Stack() {
	typeStackElem aEle[] = {{1, 2},{3, 4}, {5, 6}};
	//typeStackElem aEle[] = {};
	initStack();
	for (int i = 0; i < sizeof(aEle)/sizeof(aEle[0]) ; i++) {
		push(aEle[i]);
	}

	int i = 0;
	typeStackElem e;
	while(0 == isEmpty()) {
		e = pop();
		printf("No.%i: %i, %i\n", i, e.iL, e.iR);
		i++;
	}
}

//quickSort_NotRec()测试：非递归快速排序正式版。
void Test3() {
	clock_t start_t, end_t;
	double total_t;

	int iLen = sizeof(aTestData)/sizeof(aTestData[0]);
	printf("len=%i\n\n", iLen);
	printf("非递归快速排序，原始数据：\n");
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");

	start_t = clock();
	quickSort_NotRec(aTestData, 0, iLen-1);
	end_t = clock();
	total_t = (double)(end_t - start_t) / CLOCKS_PER_SEC;

	printf("耗时=%fs,排序后：\n", total_t);
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");
}

// quickSort_NotRec_Test()测试非递归快速排序调试版。
void Test4() {
	//int aTestData[] = {5, 2, 3, 5, 7, 3, 8, 6, 4, 9};
	//int aTestData[] = {5, 2, 3, 5, 7, 3, 8, 6, 4, 9, 15, 12, 32, 51, 75, 23, 8, 62, 24, 19, 15, 222, 5, 2, 3, 5, 7, 3, 8, 6, 4, 9, 343, 53, 67, 34, 83, 68, 46, 39};
	//int aTestData[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	int iLen = sizeof(aTestData)/sizeof(aTestData[0]);
	printf("len=%i\n\n", iLen);
	printf("原始数据：\n");
	printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");

	quickSort_NotRec_Test(aTestData, 0, iLen-1);
	printf("排序后：\n");
	printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");
}

//bubbleSort()测试冒泡排序
void Test5() {
	clock_t start_t, end_t;
	double total_t;

	int iLen = sizeof(aTestData)/sizeof(aTestData[0]);
	printf("len=%i\n\n", iLen);
	printf("冒泡排序，原始数据：\n");
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");

	start_t = clock();
	bubbleSort(aTestData, 0, iLen -1);
	end_t = clock();
	total_t = (double)(end_t - start_t) / CLOCKS_PER_SEC;
	printf("耗时=%fs,排序后：\n", total_t);
	//printArry(aTestData, 0, iLen, 0, iLen-1, -1, -1);
	printf("\n\n");
}


int main(void) {
	initTestData();

	//转储测试数列。
	clock_t start_t, end_t;
	double total_t;
	start_t = clock();

    for (int i = 0; i < MAXCOUNT; i++) {
		aTempData[i] = aTestData[i];
	}

	end_t = clock();
	total_t = (double)(end_t - start_t)/CLOCKS_PER_SEC;
    printf("total_t=%f\n", total_t);

	//Test1();
	Test2();
	//恢复测试数列。
    for (int i = 0; i < MAXCOUNT; i++) {
		aTestData[i] = aTempData[i];
	}

	Test3();
	//恢复测试数列。
    for (int i = 0; i < MAXCOUNT; i++) {
		aTestData[i] = aTempData[i];
	}

	//Test_Stack();
    //Test3();
	//Test4();
	//Test5();
	//test();
}
